package hyy_2022;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * 假设数组是非空的，并且给定的数组总是存在多数元素
 * 多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素
 */
public class _0730_169_Offer39_MajorityElement {

    public static void main(String[] args) {
        System.out.println(majorityElement(new int[] {3,2,3}));
    }


    /**
     * 用map存储, key为元素, value为元素出现的次数
     * @param nums   数组
     * @return int 数组中出现次数超过一半的数字
     */
    public static int majorityElement(int[] nums) {

        Map<Integer,Integer> map = new HashMap<>();
        for(int num : nums) {
            if(map.containsKey(Integer.valueOf(num))) {
                Integer i = map.get(Integer.valueOf(num)) ;
                map.put(Integer.valueOf(num),i+1);
            } else {
                map.put(Integer.valueOf(num),1);
            }
        }

        int element = nums.length / 2;
        for(Integer key : map.keySet()) {
            Integer value = map.get(key);
            if(value > element) {
                return key;
            }
        }
        return  0;
    }

    /**
     * 排序
     * 如果将数组nums中的所有元素按照单调递增或单调递减的顺讯排序，那么下标为[n / 2]的元素一定是众数,下标从0开始
     * @param nums
     * @return int
     */
    public static int majorityElementBySort(int[] nums) {
        //先将数组排序
        Arrays.sort(nums);
        //多数元素一定会出现在数组的[n / 2]出
        int n = nums.length;
        return n / 2;
    }

}
